package bin_tree.leetcode;

/**
 * 找二叉树的最近公共祖先
 * @author shkstart
 * @create 2022-10-25-10:46
 */
public class Num36 {

    TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
//        从根节点出发进行遍历，找到lca(p和q出现在三个位置的两个)
        find(root,p,q);
        return lca;
    }

//    在以root为根节点的二叉树中，是否能同时找到p或q
    private boolean find(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }

        int left = find(root.left,p,q)?1:0;
        int right = find(root.right,p,q)?1:0;
        int mid = (root ==p||root==q)?1:0;
        if(left+right+mid==2){
            lca =root;
            return true;
        }
        return (left+right+mid)>0;





    }
}
